package simple.linklist;

import struct.ListNode;

/**
 * <a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/">83. 删除排序链表中的重复元素</a>
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
 * 返回同样按升序排列的结果链表。
 * 示例 1：
 * 输入：head = [1,1,2]
 * 输出：[1,2]
 * 示例 2：
 * 输入：head = [1,1,2,3,3]
 * 输出：[1,2,3]
 * 提示：
 * 链表中节点数目在范围 [0, 300] 内
 * -100 <= Node.val <= 100
 * 题目数据保证链表已经按升序排列
 *
 * @author 刘学松
 * @date 2021-09-06 9:23
 */
public class 删除排序链表中的重复元素 {
    public static void main(String[] args) {
        int[] array = {1, 1, 1, 2, 2, 3, 3};
        ListNode head = new ListNode();
        ListNode currNode = new ListNode();
        head.next = currNode;
        for (int i : array) {
            currNode.next = new ListNode(i);
            currNode = currNode.next;
        }
        ListNode headNode = head.next.next;
        System.out.println("原链表：");
        while (headNode != null) {
            System.out.print(headNode.val + ", ");
            headNode = headNode.next;
        }
        ListNode listNode = deleteDuplicates(head.next.next);
        System.out.println("\n新链表：");
        while (listNode != null) {
            System.out.print(listNode.val + ", ");
            listNode = listNode.next;
        }
    }

    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        // 定义临时节点，用于定位头结点
        ListNode tempNode = new ListNode();
        tempNode.next = head;
        // 用来记录当前数
        int currVal;
        // 遍历节点
        while (head.next != null) {
            // 更新当前数
            currVal = head.val;
            // 当下个节点的值等于当前数，则当前节点的next节点指向下个节点的next
            if (head.next.val == currVal) {
                while (head.next != null && head.next.val == currVal) {
                    head.next = head.next.next;
                }
            } else {
                // 当前节点指向下一个节点
                head = head.next;
            }
        }
        // 返回头结点
        return tempNode.next;
    }
}
